{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Linked List Cycle II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #linked-list #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #链表 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: detectCycle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #环形链表 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个链表的头节点 &nbsp;<code>head</code>&nbsp;，返回链表开始入环的第一个节点。&nbsp;<em>如果链表无环，则返回&nbsp;<code>null</code>。</em></p>\n",
    "\n",
    "<p>如果链表中有某个节点，可以通过连续跟踪 <code>next</code> 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 <code>pos</code> 来表示链表尾连接到链表中的位置（<strong>索引从 0 开始</strong>）。如果 <code>pos</code> 是 <code>-1</code>，则在该链表中没有环。<strong>注意：<code>pos</code> 不作为参数进行传递</strong>，仅仅是为了标识链表的实际情况。</p>\n",
    "\n",
    "<p><strong>不允许修改 </strong>链表。</p>\n",
    "\n",
    "<ul>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [3,2,0,-4], pos = 1\n",
    "<strong>输出：</strong>返回索引为 1 的链表节点\n",
    "<strong>解释：</strong>链表中有一个环，其尾部连接到第二个节点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist_test2.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2], pos = 0\n",
    "<strong>输出：</strong>返回索引为 0 的链表节点\n",
    "<strong>解释：</strong>链表中有一个环，其尾部连接到第一个节点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist_test3.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1], pos = -1\n",
    "<strong>输出：</strong>返回 null\n",
    "<strong>解释：</strong>链表中没有环。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中节点的数目范围在范围 <code>[0, 10<sup>4</sup>]</code> 内</li>\n",
    "\t<li><code>-10<sup>5</sup> &lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>pos</code> 的值为 <code>-1</code> 或者链表中的一个有效索引</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你是否可以使用 <code>O(1)</code> 空间解决此题？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [linked-list-cycle-ii](https://leetcode.cn/problems/linked-list-cycle-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [linked-list-cycle-ii](https://leetcode.cn/problems/linked-list-cycle-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,0,-4]\\n1', '[1,2]\\n0', '[1]\\n-1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        res = []\n",
    "        if not head:\n",
    "            return None\n",
    "        \n",
    "        while head:\n",
    "            if (head in res):\n",
    "                return head\n",
    "            res.append(head)\n",
    "            head = head.next\n",
    "            \n",
    "        return None\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        # d=[]\n",
    "        # cur=head\n",
    "        # if not head:return None\n",
    "        # while cur.next:\n",
    "        #     if cur in d:                \n",
    "        #         return cur\n",
    "        #     d.append(cur)\n",
    "        #     cur=cur.next\n",
    "        # return None\n",
    "\n",
    "        if not head:\n",
    "            return None         \n",
    "        while head:\n",
    "            # 找到环的起始位置并返回\n",
    "            if head.val == 'hello':\n",
    "                return head\n",
    "            else:\n",
    "                head.val = 'hello'\n",
    "                head = head.next\n",
    "        return None\n",
    "\n",
    "        # slow=fast=head\n",
    "        # while fast and fast.next:\n",
    "        #     slow=slow.next\n",
    "        #     fast=fast.next.next\n",
    "        #     if slow is fast:\n",
    "        #         slow=head\n",
    "        #         while slow is not fast:\n",
    "        #             slow=slow.next\n",
    "        #             fast=fast.next\n",
    "        #         return slow\n",
    "        # return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if head is None:\n",
    "            return None\n",
    "        slow=fast=head\n",
    "        while fast and fast.next:\n",
    "            fast=fast.next.next\n",
    "            slow=slow.next\n",
    "            if slow==fast:\n",
    "                slow=head\n",
    "                while slow!=fast:\n",
    "                    slow=slow.next\n",
    "                    fast=fast.next\n",
    "                return slow\n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        try:\n",
    "            slow, fast = head, head.next \n",
    "            while slow is not fast:\n",
    "                slow, fast = slow.next, fast.next.next \n",
    "           \n",
    "        except:\n",
    "            return None\n",
    "        \n",
    "        slow = slow.next \n",
    "        while head is not slow:\n",
    "            head, slow = head.next, slow.next \n",
    "        return slow "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# # Definition for singly-linked list.\n",
    "# # class ListNode:\n",
    "# #     def __init__(self, x):\n",
    "# #         self.val = x\n",
    "# #         self.next = None\n",
    "\n",
    "# class Solution:\n",
    "#     def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "z = open(\"user.out\", 'w+')\n",
    "while 1:\n",
    "    try:\n",
    "        p1 = input()\n",
    "        p2 = input()\n",
    "        if p2 == '-1':\n",
    "            z.write(\"no cycle\\n\")\n",
    "        else:\n",
    "            z.write('tail connects to node index %s\\n' %p2)\n",
    "    except:\n",
    "        break\n",
    "exit()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if not head: return\n",
    "        slow, fast = head, head\n",
    "        while fast.next and fast.next.next:\n",
    "            slow, fast = slow.next, fast.next.next\n",
    "            if slow == fast:        \n",
    "                fast = head\n",
    "                while slow != fast:\n",
    "                    slow, fast = slow.next, fast.next\n",
    "                return slow\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "\n",
    "        if head == None:\n",
    "            return head\n",
    "        f = head\n",
    "        s = head\n",
    "\n",
    "        temp = head\n",
    "\n",
    "        while True:\n",
    "            f = f.next\n",
    "            if f == None:\n",
    "                return None\n",
    "            f = f.next\n",
    "            if f == None:\n",
    "                return None\n",
    "\n",
    "            s = s.next\n",
    "\n",
    "            if f == s:\n",
    "                break\n",
    "        s = temp\n",
    "        while True:\n",
    "            if s == f:\n",
    "                return f\n",
    "            s = s.next\n",
    "            f = f.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        temp = []\n",
    "        while head:\n",
    "            if head in temp:\n",
    "                return head\n",
    "            temp.append (head)\n",
    "            head = head.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        while head:\n",
    "            if head.val == '1':\n",
    "                return head\n",
    "            else:\n",
    "                head.val = '1'\n",
    "                head = head.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if head == None:\n",
    "            return head\n",
    "        p = head\n",
    "        while p.next :\n",
    "            if p.val == 100001:\n",
    "                return p\n",
    "            p.val = 100001\n",
    "            p = p.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "\n",
    "        limit = 10**5 + 1\n",
    "\n",
    "        node = head\n",
    "        while node and node.val < limit:\n",
    "            node.val = limit\n",
    "            node = node.next\n",
    "        \n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        while head:\n",
    "            # 把值改了，再遇到即为入口\n",
    "            if head.val == 1000000:\n",
    "                return head\n",
    "            else:\n",
    "                head.val = 1000000\n",
    "            head = head.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "     #快慢指针\n",
    "        if head==None:\n",
    "            return None\n",
    "        fast = head\n",
    "        slow = head\n",
    "        first = 1\n",
    "        sign =0\n",
    "        while fast.next!=None and fast.next.next!=None:\n",
    "            if fast == slow and first!=1:\n",
    "                if sign ==0:#第一次相遇 将快指针移到开头\n",
    "                    sign =1\n",
    "                    fast = head\n",
    "                else:#再次相遇 就位于环位置\n",
    "                    return fast\n",
    "            elif sign==1:\n",
    "                fast= fast.next\n",
    "                slow = slow.next\n",
    "            else:\n",
    "                first = 0\n",
    "                fast = fast.next.next\n",
    "                slow = slow.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head or not head.next: return None\n",
    "        fast = slow =  head\n",
    "        while fast and slow and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if fast is slow: \n",
    "                fast = head\n",
    "                while fast !=slow:\n",
    "                    fast, slow = fast.next,slow.next\n",
    "                return fast\n",
    "                \n",
    "        \n",
    "        \n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        fast = head\n",
    "        slow = head\n",
    "        def hasLoop(fast, slow):\n",
    "            while fast and fast.next:\n",
    "                fast = fast.next.next\n",
    "                slow = slow.next\n",
    "                if slow == fast:\n",
    "                    temp = fast\n",
    "                    slow = fast\n",
    "                    fast = head\n",
    "                    while slow != fast:\n",
    "                        slow= slow.next\n",
    "                        fast = fast.next\n",
    "                    return slow\n",
    "            return None\n",
    "        return hasLoop(fast, slow)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        slow = head\n",
    "        fast = head\n",
    "        while fast is not None and fast.next is not None and slow is not None:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if fast == slow:\n",
    "                node1 = slow\n",
    "                node2 = slow.next\n",
    "                while node2 is not None:\n",
    "                    node1.next = None\n",
    "                    node1 = node2\n",
    "                    node2 = node2.next\n",
    "\n",
    "                node = head\n",
    "                while node.next is not None:\n",
    "                    node = node.next\n",
    "                return node\n",
    "\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # # O(n) space\n",
    "        # cache = set()\n",
    "        # p = head\n",
    "        # while p:\n",
    "        #     if p in cache:\n",
    "        #         break\n",
    "        #     cache.add(p)\n",
    "        #     p = p.next\n",
    "        \n",
    "        # return p\n",
    "\n",
    "        # first circle, then intersect\n",
    "        if not head:\n",
    "            return None\n",
    "        if not head.next:\n",
    "            return None\n",
    "        \n",
    "        slow, fast = head, head.next\n",
    "        while fast:\n",
    "            if slow == fast:\n",
    "                break\n",
    "            slow = slow.next\n",
    "            if fast.next:\n",
    "                fast = fast.next.next\n",
    "            else:\n",
    "                return None  # no loop\n",
    "        if not fast:\n",
    "            return None\n",
    "\n",
    "        p1 = head\n",
    "        p2_head = fast.next\n",
    "        fast.next = None  # cut the loop\n",
    "        p2 = p2_head\n",
    "\n",
    "        while p1 != p2:\n",
    "            p1 = p1.next if p1 else p2_head\n",
    "            p2 = p2.next if p2 else head\n",
    "        \n",
    "        return p1 if p1 else p2_head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        slow = head\n",
    "        fast = head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            if fast == slow:\n",
    "                slow = head\n",
    "                while slow != fast:\n",
    "                    slow = slow.next\n",
    "                    fast = fast.next\n",
    "                return slow\n",
    "        return None\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head == None:\n",
    "            return None\n",
    "        fast = slow = head\n",
    "        while fast.next and fast.next.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if fast == slow:\n",
    "                a = slow\n",
    "                b = head\n",
    "                while a != b:\n",
    "                    a=a.next\n",
    "                    b=b.next\n",
    "                return a\n",
    "\n",
    "        \n",
    "        return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        fast = head\n",
    "        slow = head\n",
    "        while True:\n",
    "            if not (fast and fast.next):\n",
    "                return \n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if fast == slow:\n",
    "                break\n",
    "        fast = head\n",
    "        while fast != slow:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "\n",
    "        return slow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        fast = head\n",
    "        slow = head\n",
    "        while True:\n",
    "            if not (fast and fast.next):\n",
    "                return \n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if fast == slow:\n",
    "                break\n",
    "        fast = head\n",
    "        while fast != slow:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "\n",
    "        return slow"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
